﻿#define _CRT_SECURE_NO_WARNINGS 1
#include "RBTree.h"
#include <vector>
void RBTreeTest1()
{
	Aurora::RBTree<int, int> rb;
	//常规测试用例
	//int a[] = { 16,3,7,11,9,26,18,14,15 };
	//带有双旋场景的测试用例
	int a[] = { 4,2,6,1,3,5,15,7,16,14 };
	for (const auto& e : a)
	{
		rb.Insert({ e,e });
	}
	rb.InOrder();
	cout << rb.IsBalance() << endl;
	cout << rb.Hight() << endl;
	cout << rb.Size() << endl;
}
void RBTreeTest2()
{
	const size_t N = 10000000;
	Aurora::RBTree<int, int> rb;
	vector<int> v;
	srand(time(nullptr));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
	int begin1 = clock();
	for (const auto& e : v)
	{
		rb.Insert({ e,e });
	}
	int end1 = clock();
	int begin2 = clock();
	int x = rand();
	Aurora::RBTNode<int,int>* f = rb.Find(x);
	if (f != nullptr)
	{
		cout << "找到了:" << f->_kv.first << ":" << f->_kv.second << endl;
	}
	else
	{
		cout << "没找到" << endl;
	}
	int end2 = clock();
	cout << "Insert:" << end1 - begin1 << "ms" << endl;
	cout << "Find:" << end2 - begin2 << "ms" << endl;
	cout << "Hight:" << rb.Hight() << "层" << endl;
	cout << "Size:" << rb.Size() << "个" << endl;
	cout << "是否为红黑树:" << rb.IsBalance() << endl;
}
int main()
{
	RBTreeTest2();
	return 0;
}
/*
2025.1.24 假期学习打卡第十五天 红黑树的实现
红黑树的实现和AVL树的实现是很相似的,AVL树是严格
平衡,而红黑树的接近平衡,但是红黑树理解起来特别
抽象,但是学会了就会发现比AVL树还简单,但是效率会
比AVL树低一点点,但是也可以忽略不计,约等于logN,
红黑树插入一千万个数据,高度才达到33层,而查找的
效率也是非常高的,一千万个随机值中查找只需要2ms。
*/